/*
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n==0) return {};
		if(n==1) return {"()"};
		vector<vector<string>> dp(n+1);
		dp[0]={""};
		dp[1]={"()"};
		for(int i=2;i<=n;i++){
			for(int j=0;j<i;j++){
				for(string p:dp[j])
					for(string q:dp[i-j-1]){
						string str="(" + p + ")" + q;
						dp[i].push_back(str);
					}
			}
		} 
		return dp[n]; 
    }
};

/*
    dp[i]表示i组括号的所有有效组合
    在i个括号的排列组合时，把i个括号中单独拿出来一个括号，剩下的i-1个括号分为两部分，
    p个括号和q个括号，p+q=i-1，然后p个括号在单独拿出来的那个括号里面，q个括号在单独拿出来的那个括号右边
    然后再各自进行排列组合

    c++ 11的新特性，for(type i : 数组 ) ，这样写 i相当于迭代器，会遍历数组中每个元素。
    for(string p :dp[j] ) 是遍历dp[j]中的每个string
*/